package com.game.astar;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import com.game.astar.entity.Node;
import com.game.astar.mode.DirectionEnum;
import com.game.astar.util.SceneConfig;

/**
 * 寻路驱动
 * @author 庄宏晓
 * @date 2013-6-9
 */
public class DDAStarDrive 
{
	static NodeComparator compa = new NodeComparator();
	
	/**
	 * 开放列表
	 */
	List<Node> openList = new ArrayList<Node>();
	/**
	 * 关闭列表
	 */
	List<Node> closeList = new ArrayList<Node>();
	
	/**
	 * 路径搜索
	 * @param x	起始坐标X
	 * @param y	起始坐标Y
	 * @param endX	终点坐标X
	 * @param endY	终点坐标Y
	 * @param map	地图数据
	 * @create 2013-6-13 庄宏晓
	 */
	public boolean searchPath(int x, int y, int endX, int endY, char[][] map)
	{
		/*地点异常*/
		if(map[y][x] == SceneConfig.STOPCHAR || map[endY][endX] == SceneConfig.STOPCHAR)
		{
			return Boolean.FALSE;
		}
		
		/*创建起始点和终点*/
		Node startNode = createNode(x, y, 0, null);
		Node endNode = createNode(endX, endY, 0, null);
		
		/*开放列表添加起始点*/
		openList.add(startNode);
		
		/*搜索路径*/
		endNode = search(startNode, endNode, map);
		
//		System.out.println(">>> 寻路完毕!");
		if(endNode != null)
		{
			/*设置最终路径*/
//			System.out.println(">>> 设置路劲!");
			getPath(map, startNode, endNode);
			return Boolean.TRUE;
		}
		else
		{
			return Boolean.FALSE;
		}
		
	}
	
	/**
	 * 设置路径线路
	 * @param map	地图数据
	 * @param startNode 起点
	 * @param endNode	终点
	 * @create 2013-6-13 庄宏晓
	 */
	private void getPath(char[][] map, Node startNode, Node endNode) 
	{
		while(!(endNode.getX() == startNode.getX() && endNode.getY() == startNode.getY()))
		{	
			endNode = endNode.getParentNode();
			
			if(endNode.getX() == startNode.getX() && endNode.getY() == startNode.getY())
			{
				continue;
			}
			
			map[endNode.getY()][endNode.getX()] = SceneConfig.PATHCHAR;
		}
	}

	/**
	 * 搜索路径
	 * @param startNode	起始点
	 * @param endNode	终点
	 * @create 2013-6-13 庄宏晓
	 */
	private Node search(Node startNode, Node endNode, char[][] map) 
	{
		while(!openList.isEmpty())
		{
			/*获取一个点*/
			Node node = openList.remove(0);
			
			if(node.equals(endNode))
			{
				return node;
			}
			
			/*寻找子节点*/
//			/*上下左右, 左上,左下,右上,右下*/
//			findChild(DirectionEnum.UP, map, endNode, node);
//			findChild(DirectionEnum.DOWN, map, endNode, node);
//			findChild(DirectionEnum.LEFT, map, endNode, node);
//			findChild(DirectionEnum.RIGHT, map, endNode, node);
//			findChild(DirectionEnum.LEFT_UP, map, endNode, node);
//			findChild(DirectionEnum.LEFT_DOWN, map, endNode, node);
//			findChild(DirectionEnum.RIGHT_UP, map, endNode, node);
//			findChild(DirectionEnum.RIGHT_DOWN, map, endNode, node);
			
			for (DirectionEnum direction : DirectionEnum.values()) 
			{
				findChild(direction, map, endNode, node);
			}
		}
		
		return null;
	}
	
	/**
	 * 按方向寻找
	 * @param direction	方向
	 * @param map	地图数据
	 * @param endNode	终点
	 * @param node		父点
	 * @create 2013-6-13 庄宏晓
	 */
	void findChild(DirectionEnum direction, char[][] map, Node endNode, Node node)
	{
		int x = node.getX() + direction.getX();
		int y = node.getY() + direction.getY();
		
		/*坐标异常*/
		if(x < 0 || y < 0 || y >= map.length || x >= map[y].length - 1 || map[node.getY()][node.getX()] == SceneConfig.STOPCHAR)
		{
			return;
		}
		
		int h = (Math.abs(endNode.getX() - x) + Math.abs(endNode.getY() - y)) * 10;
		
		Node child = createNode(x, y, direction.getG() + h, node);
		
		int indexOpen = openList.indexOf(child);
		int indexClose = closeList.indexOf(child);
		
		/*新子类*/
		if(indexOpen == -1 && indexClose == -1)
		{
			openList.add(child);
		}
		else if(indexOpen != -1)
		{
			/*节点已存在*/
			if(child.getF() < openList.get(indexOpen).getF())
			{
				/*更新评估值*/
				openList.get(indexOpen).setF(child.getF());
			}
		}
		else
		{
			/*搜索废弃的节点*/
			if(child.getF() < closeList.get(indexClose).getF())
			{
				/*更新评估值*/
				closeList.remove(indexClose);
				openList.add(child);
			}
		}
		
		closeList.add(node);
		Collections.sort(openList, compa);
	}

	/**
	 * 创建一个子节点
	 * @param x	坐标x
	 * @param y 坐标y
	 * @param f 评估值
	 * @param parentNode	父节点
	 * @return	子节点
	 * @create 2013-6-13 庄宏晓
	 */
	static Node createNode(int x, int y, int f, Node parentNode)
	{
		return new Node(x, y, f, parentNode);
	}
	
	/**
	 * 节点排序规则
	 * @author 庄宏晓
	 * @date 2013-6-9
	 */
	static class NodeComparator implements Comparator<Node>
	{
		public NodeComparator() {}
		
		@Override
		public int compare(Node o1, Node o2) 
		{
			return o1.getF() - o2.getF();
		}
		
	}
}
